package algorithm.sort;

public class Merge extends Common implements Sort {
    QuickSort quickSort = new QuickSort(ImplementType.DFS);

    @Override
    public void execute(int[] nums) {
        execute(nums, this.type);
    }

    @Override
    public void execute(int[] nums, ImplementType methodType) {
        // sort4(new int[nums.length], nums, 0, nums.length - 1);
        merge2(new int[nums.length], nums, 0, nums.length - 1);
    }

    public void merge2(int[] temp, int[] nums, int left, int right) {
     /*   if (left >= right) {
            return;
        }*/
        if ((right - left) < 100) {
            quickSort.quickSort(nums, left, right);
            return;
        }
        int mid = (left + right) >> 1;
        merge2(temp, nums, left, mid);
        merge2(temp, nums, mid + 1, right);
        merge_data(temp, nums, left, mid, right);

    }

    public void merge3(int[] temp, int[] nums, int left, int right) {
        if ((right - left) < 100) {
            quickSort.quickSort(nums, left, right);
            return;
        }
        int thired = (right - left) / 3 + left;
        int two_thired = (right - left) * 2 / 3 + left;
        merge3(temp, nums, left, thired);
        merge3(temp, nums, thired + 1, two_thired);
        merge3(temp, nums, two_thired + 1, right);
        merge_data(temp, nums, left, thired, two_thired);
        merge_data(temp, nums, left, two_thired, right);

    }

    public void merge_data(int[] temp, int[] nums, int left, int mid, int right) {
        int i = left, j = mid + 1, index = left;
        for (; i <= mid && j <= right; index++) {
            if (nums[i] > nums[j]) {
                temp[index] = nums[j++];
            } else {
                temp[index] = nums[i++];
            }
        }
        for (; i <= mid; i++, index++) {
            temp[index] = nums[i];
        }
        for (; j <= right; j++, index++) {
            temp[index] = nums[j];
        }
        for (int k = left; k <= right; k++) {
            nums[k] = temp[k];
        }
    }

    public void sort4(int[] temp, int[] nums, int left, int right) {
        int MAX_RUN_COUNT = 30000000;
        int[] run = new int[MAX_RUN_COUNT * 2 + 5];
        int count = 0;
        run[0] = left;

        // Check if the array is nearly sorted
        for (int k = left; k < right; run[count] = k) {
            if (nums[k] < nums[k + 1]) { // ascending
                while (++k <= right && nums[k - 1] <= nums[k])
                    ;
            } else if (nums[k] > nums[k + 1]) { // descending
                while (++k <= right && nums[k - 1] >= nums[k])
                    ;
                for (int lo = run[count] - 1, hi = k; ++lo < --hi;) {
                    swap(nums, hi, lo);
                }
            } else { // equal
                for (int m = nums.length; ++k <= right && nums[k - 1] == nums[k];) {
                    if (--m == 0) {
                        merge2(temp, nums, left, right);
                        return;
                    }
                }
            }

            /*
             * The array is not highly structured, use Quicksort instead of
             * merge sort.
             */
            if (++count == MAX_RUN_COUNT) {
                merge2(temp, nums, left, right);
                return;
            }
        }

        // Check special cases
        // Implementation note: variable "right" is increased by 1.
        if (run[count] == right++) { // The last run contains one element
            run[++count] = right;
        } else if (count == 1) { // The array is already sorted
            return;
        }
        merge_data(temp, nums, run, 0, count);
    }

    public void merge_data(int[] temp, int[] nums, int[] run, int leftC, int rightC) {
        if (rightC - leftC == 2) {
            merge_data(temp, nums, run[leftC], run[leftC + 1] - 1, run[rightC] - 1);
        } else if (rightC - leftC <= 1) {
            return;
        }
        int mid = (leftC + rightC) / 2;
        merge_data(temp, nums, run, leftC, mid);
        merge_data(temp, nums, run, mid, rightC);
        merge_data(temp, nums, run[leftC], run[mid] - 1, run[rightC] - 1);
    }
}
